//方法一：多状态dp
//维护一个 n * 2的dp表
//对于第i行
//第一列，第i天处于可买入状态的最大利润：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + p[n])
//第二列，第i天处于可卖出状态的最大利润：dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - p[n])
// class Solution {
// public:
//     int maxProfit(vector<int>& prices) {
//         int n = prices.size();
//         vector<vector<int>> dp(n, vector<int>(2, 0));
//         dp[0][1] = -prices[0];

//         for (int i = 1; i < prices.size(); i++)
//         {
//             dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
//             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//         }

//         return dp[n - 1][0];
//     }
// };

// //方法二：贪心
// //把所有的“上坡”买到，就是利益最大化
// class Solution {
// public:
//     int maxProfit(vector<int>& prices) {
//         int n = prices.size();
//         int sum = 0;
//         for (int i = 1; i < n; i++)
//         {
//             if (prices[i] > prices[i - 1])
//                 sum += prices[i] - prices[i - 1];
//         }

//         return sum;
//     }
// };

//方法二：贪心 + 双指针
//把所有的“上坡”买到，就是利益最大化
//用双指针找到每一段上坡[slow, fast)
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        int sum = 0;
        int slow = 0, fast = 1;
        prices.push_back(INT_MIN);  //防止出现数组递增的情况
        while (fast < n + 1)
        {
            if (prices[fast] <= prices[fast - 1])
            {
                sum += prices[fast - 1] - prices[slow];
                slow = fast;
            }
            fast++;
        }
        prices.pop_back();
        return sum;
    }
};